package nachos.threads;

import nachos.machine.*;

import java.util.TreeSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.ArrayList;

/**
 * A scheduler that chooses threads based on their priorities.
 *
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the
 * thread that has been waiting longest.
 *
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fassion to
 * all the highest-priority threads, and ignores all other threads. This has
 * the potential to
 * starve a thread if there's always a thread waiting with higher priority.
 *
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 */
public class PriorityScheduler extends Scheduler {
    /**
     * Allocate a new priority scheduler.
     */
    public PriorityScheduler() {
    }
    
    /**
     * Allocate a new priority thread queue.
     *
     * @param	transferPriority	<tt>true</tt> if this queue should
     *					transfer priority from waiting threads
     *					to the owning thread.
     * @return	a new priority thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {
	return new PriorityQueue(transferPriority);
    }

    public int getPriority(KThread thread) {
	Lib.assertTrue(Machine.interrupt().disabled());
		       
	return getThreadState(thread).getPriority();
    }

    public int getEffectivePriority(KThread thread) {
	Lib.assertTrue(Machine.interrupt().disabled());
		       
	return getThreadState(thread).getEffectivePriority();
    }

    public void setPriority(KThread thread, int priority) {
	Lib.assertTrue(Machine.interrupt().disabled());
		       
	Lib.assertTrue(priority >= priorityMinimum &&
		   priority <= priorityMaximum);
	
	getThreadState(thread).setPriority(priority);
    }

    public boolean increasePriority() {
	boolean intStatus = Machine.interrupt().disable();
		       
	KThread thread = KThread.currentThread();

	int priority = getPriority(thread);
	if (priority == priorityMaximum)
	    return false;

	setPriority(thread, priority+1);

	Machine.interrupt().restore(intStatus);
	return true;
    }

    public boolean decreasePriority() {
	boolean intStatus = Machine.interrupt().disable();
		       
	KThread thread = KThread.currentThread();

	int priority = getPriority(thread);
	if (priority == priorityMinimum)
	    return false;

	setPriority(thread, priority-1);

	Machine.interrupt().restore(intStatus);
	return true;
    }

    /**
     * The default priority for a new thread. Do not change this value.
     */
    public static final int priorityDefault = 1;
    /**
     * The minimum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMinimum = 0;
    /**
     * The maximum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMaximum = 7;    

    /**
     * Return the scheduling state of the specified thread.
     *
     * @param	thread	the thread whose scheduling state to return.
     * @return	the scheduling state of the specified thread.
     */
    protected ThreadState getThreadState(KThread thread) {
	if (thread.schedulingState == null)
	    thread.schedulingState = new ThreadState(thread);

	return (ThreadState) thread.schedulingState;
    }

    
    /**
     * A <tt>ThreadQueue</tt> that sorts threads by priority.
     */
    protected class PriorityQueue extends ThreadQueue {

	    protected ArrayList threadList = new ArrayList();
	    protected KThread owner = null;
	    
	    PriorityQueue(boolean transferPriority) {
		    this.transferPriority = transferPriority;
	    }

	    public void waitForAccess(KThread thread) {
		    Lib.assertTrue(Machine.interrupt().disabled());
		    
  		    KThread threadTmp = null; 
		    //When I wait for a queue, I might change the effective
		    //priority of that queue's threads because of my priority. 
		    for (int i = 0; i < threadList.size(); i++){
			threadTmp = (KThread)threadList.get(i);
			getThreadState(thread).invalidatePriority();
		    }
          //threadList.offer(thread);
	            threadList.add(thread);
		    getThreadState(thread).waitForAccess(this);
	    }

	    public void acquire(KThread thread) {
		    Lib.assertTrue(Machine.interrupt().disabled());
		    //Lib.assertTrue(threadList.isEmpty());
		    owner = thread;
		    getThreadState(thread).acquire(this);
	    }

	    public KThread nextThread() {
		 	boolean intStatus = Machine.interrupt().disable();
		       
	   
          Lib.assertTrue(Machine.interrupt().disabled());

          if (owner != null){
             getThreadState(owner).removeQueue(this); //The current owner gives up control of this queue
          }
		    
	  //Return null if no one is in the list
          if (isEmpty()){
             owner = null;
	          Machine.interrupt().restore(intStatus);
			    return null;
		    }
	
	  //Find the next thread to pick
          owner = pickNextThread().thread;

	  //Assign the new owner
	  if (owner != null){
		  getThreadState(owner).invalidatePriority(); //I no longer own this lock and my priority may change
        	  threadList.remove(owner);  //I am no longer waiting in the list
	          acquire(owner);            //I should acquire the lock
	  }
	  Machine.interrupt().restore(intStatus);
          return owner;
	    }

	    public boolean isEmpty() {
		    return threadList.isEmpty();
	    }

	    /**
	     * Return the next thread that <tt>nextThread()</tt> would return,
	     * without modifying the state of this queue.
	     *
	     * @return	the next thread that <tt>nextThread()</tt> would
	     *		return.
	     */
	    protected ThreadState pickNextThread() {
		    // (Brian) How is this different from nextThread()?
          // (Kyle) This is like a peek() rather than a pop(), it doesn't
          // actually take it out of the queue.
		    if (isEmpty()){
			    return null;
		    }
		    
	       int position = 0;
		    int max = 0;
		    int current = 0;
		    long oldestTime = System.currentTimeMillis();
		    long currentTime = 0;

		    //Find the maximum priority and waitingTimes for all of the threads that
		    //are waiting for this queue. If priorities are equivalent, checking 
		    //for the oldest time.
		    //
		    for (int i = 0; i < threadList.size(); i++){
			    KThread thread = (KThread) threadList.get(i);
		
			    //If transferPriority, use effective, otherwise, use normal.
			    if (transferPriority){
				    current = getThreadState(thread).getEffectivePriority();
				    //current = getThreadState(thread).getPriority();
				   //System.out.println("Transfer P Name : " + thread.getName() + " p: " + current);
			    }
			    else {
				   // current = getThreadState(thread).getEffectivePriority();
                		   current = getThreadState(thread).getPriority();
				   //System.out.println("P Name : " + thread.getName() + " p: " + current);
			    }

			    //Reassign max
			    if (current > max){
				    max = current;
				    position = i;
				    oldestTime = currentTime;
			    }
			    //If they are the same, check for oldest
			    else if (current == max){
				    currentTime = getThreadState(thread).getWaitingTime();
				    if (currentTime < oldestTime){
					    oldestTime = currentTime;
					    position = i;
				    }
			    }
		    }
          //return getThreadState((KThread) threadList.poll());
          //System.out.println("ThreadList size: " + threadList.size());
          //System.out.println("Scheduling Thread: " + ((KThread)threadList.get(position)).getName() + " with p: " + max);
          return getThreadState((KThread) threadList.get(position));
       }

       


	    public void print() {
		    Lib.assertTrue(Machine.interrupt().disabled());
		    // implement me (if you want)
	    }

	    /**
	     * <tt>true</tt> if this queue should transfer priority from waiting
	     * threads to the owning thread.
	     */
	    public boolean transferPriority;

	    public ArrayList getThreadList(){
		return threadList;
	    }
    }

    /**
     * The scheduling state of a thread. This should include the thread's
     * priority, its effective priority, any objects it owns, and the queue
     * it's waiting for, if any.
     *
     * @see	nachos.threads.KThread#schedulingState
     */
    protected class ThreadState implements Comparable {

	    protected ArrayList aquiredList = new ArrayList();
       protected long waitingTime = System.currentTimeMillis();
	protected int effectivePriority = -1;
	protected int recalcPriority = -1;
       
	 /**
	 * Allocate a new <tt>ThreadState</tt> object and associate it with the
	 * specified thread.
	 *
	 * @param	thread	the thread this state belongs to.
	 */
	public ThreadState(KThread thread) {
	    this.thread = thread;
	    setPriority(priorityDefault);
	}

	/**
	 * Return the priority of the associated thread.
	 *
	 * @return	the priority of the associated thread.
	 */
	public int getPriority() {
	    return priority;
	}

	/**
	 * Return the effective priority of the associated thread.
	 *
	 * @return	the effective priority of the associated thread.
	 */
	public int getEffectivePriority() {
		PriorityQueue waitQueue = null;
		ArrayList threads = null;
		int max = priority;
		int current = 0;

		//Search through the threads from the waitingQueues that I own and 
		//threads in queues that those threads own.
		//If any of their priorities is higher than mine, then use the highest.
		if (effectivePriority == recalcPriority){ //First check whether there was a possible priority change
			for (int i = 0; i < aquiredList.size(); i++){
				waitQueue = (PriorityQueue) aquiredList.get(i);		
				threads = waitQueue.getThreadList();
				for (int j = 0; j < threads.size(); j++){
					current = ((ThreadState)((KThread)threads.get(j)).schedulingState).getEffectivePriority();
					if (current > max){
						max = current;
						effectivePriority = max;
					}
				}	
			}	    
		}
		if (effectivePriority == -1){
			effectivePriority = getPriority();
		}
		return effectivePriority;
	}

   /**
	 * Set the priority of the associated thread to the specified value.
	 *
	 * @param	priority	the new priority.
	 */
	public void setPriority(int priority) {

		//Ensure that the priority being set is not greater than or less 
		//than the max/min. Also inform that the effective priority must 
		//be calculated again.
		if (this.priority == priority){
			return;
		}
		else if (priority > PriorityScheduler.priorityMaximum){
			this.priority = PriorityScheduler.priorityMaximum;
		}
		else if (priority < PriorityScheduler.priorityMinimum){
			this.priority = PriorityScheduler.priorityMinimum;
		}
		else{
			this.priority = priority;
		}
		effectivePriority = recalcPriority;
       	
	}

	/**
	 * Called when <tt>waitForAccess(thread)</tt> (where <tt>thread</tt> is
	 * the associated thread) is invoked on the specified priority queue.
	 * The associated thread is therefore waiting for access to the
	 * resource guarded by <tt>waitQueue</tt>. This method is only called
	 * if the associated thread cannot immediately obtain access.
	 *
	 * @param	waitQueue	the queue that the associated thread is
	 *				now waiting on.
	 *
	 * @see	nachos.threads.ThreadQueue#waitForAccess
	 */
	public void waitForAccess(PriorityQueue waitQueue) {
		//I am waiting for the queue, and time stamp my initial time
	     	waitingTime = System.currentTimeMillis();
	}

	/**
	 * Called when the associated thread has acquired access to whatever is
	 * guarded by <tt>waitQueue</tt>. This can occur either as a result of
	 * <tt>acquire(thread)</tt> being invoked on <tt>waitQueue</tt> (where
	 * <tt>thread</tt> is the associated thread), or as a result of
	 * <tt>nextThread()</tt> being invoked on <tt>waitQueue</tt>.
	 *
	 * @see	nachos.threads.ThreadQueue#acquire
	 * @see	nachos.threads.ThreadQueue#nextThread
	 */
	public void acquire(PriorityQueue waitQueue) {
		//I aquire the queue and add the queue to my owned list
    		aquiredList.add(waitQueue);

	    //I now own a new lock and my effectivePriority may change.
	    effectivePriority = recalcPriority;
	}	

   //returns the time I've been waiting
   public long getWaitingTime(){
      return waitingTime;
   }

   //Removes a queue from my owned list
   public void removeQueue(PriorityQueue queue){
	aquiredList.remove(queue);
   }

   //Informs the thread that the effective priority needs to be updated
   public void invalidatePriority(){
	effectivePriority = recalcPriority;
   }
   /** The thread with which this object is associated. */	   
	protected KThread thread;
	/** The priority of the associated thread. */
	protected int priority;
   
   public int compareTo(Object obj){
      long waitingTime1 = (this.waitingTime);
      long waitingTime2 = (((ThreadState)obj).waitingTime);
      long priority1 = (this.priority);
      long priority2 = (((ThreadState)obj).priority);
      if (priority1 > priority2){
         return -1;
      }
      else if (priority1 < priority2){
         return 1;
      }
      else{
         if(waitingTime1 < waitingTime2){
            return -1;
         }
         else if (waitingTime1 > waitingTime2){
            return 1;
         }
         else{
            return 0;
         }
      }
   }

   public boolean equals(Object obj){
      if (this.waitingTime == ((ThreadState)obj).waitingTime && this.priority == ((ThreadState)obj).priority)
         return true;
      return false;

   }


    }


}
